#include <iostream>
#include <fstream>
#include "BiGraph.h"

using namespace std;

pair<int, int> readGraph(BiGraph< int >& graph) {
    ifstream input("in.txt", ifstream::in);
    if (!input.is_open()) {
        cout<<"No input file!\n";
        system("pause");
        exit(1);
    }
    
    int n = 0;
    input>>n;
    
    int a, b;
    input>>a>>b;
    
    int f, t;
    double w;
    
    while (input.good()) {
          input>>f>>t>>w;
          graph.add_edge(f ,t, w);
    }

    return make_pair(a,b);
}

int main() {
    BiGraph<int> graph(true);
    pair<int,int> edge = readGraph(graph); 
    double lowest = 0;
    vector<int> path;
        
    graph.Bellman_Ford(graph.get_vertex(edge.first));
    
    BiGraph<int>::Vertex* finish = graph.get_vertex(edge.second);
    
    while (finish->parent) {
          path.push_back(finish->get_name());
          lowest += graph.get_edge(finish->parent->get_name(), finish->get_name())->get_weight();
          finish = finish->parent;
    }
    path.push_back(edge.first);
    
    reverse(path.begin(), path.end());
    
    int remove1 = 0;
    int remove2 = 0;
    double remove_w = 0;
    double minpath = numeric_limits<double>::max();
    
    for (int r = 0; r < path.size() - 1; ++r) {
        remove1 = path[r];
        remove2 = path[r+1];
        remove_w = graph.get_edge(remove1, remove2)->get_weight();
        graph.delete_edge(remove1, remove2);
        
        graph.init();
        graph.Bellman_Ford(graph.get_vertex(edge.first));
        finish = graph.get_vertex(edge.second);
        double weight = 0;
        if (finish->parent) {
            while (finish->parent) {
              weight += graph.get_edge(finish->parent->get_name(), finish->get_name())->get_weight();
              finish = finish->parent;
            }
        
            if (weight < minpath) {
                minpath = weight;
            }
        }
        graph.add_edge(remove1, remove2, remove_w);
    }
    if (minpath < numeric_limits<double>::max()) cout<<"YES "<<minpath<<endl;
    else cout<<"NO"<<endl;
    
    system("pause");
    
    return 0;
}
